package chapter03_binaryTree;

import java.util.HashMap;

/**
 * 描述：
 *      找到二叉树中累加和为指定值的最长路径长度，路径是从某个结点往下
 * @author hl
 * @date 2021/5/6 9:57
 */
public class GetMaxLength {

    public static void main(String[] args) {
        Node head = new Node(-3);
        head.left = new Node(3);
        head.left.left = new Node(1);
        head.left.right = new Node(0);
        head.left.right.left = new Node(1);
        head.left.right.right = new Node(6);
        head.right = new Node(-9);
        head.right.left = new Node(2);
        head.right.right = new Node(1);
        int maxLength = new GetMaxLength().getMaxLength(head, 6);
        System.out.println(maxLength);
    }


    public int getMaxLength(Node root, int sum){
        if (root == null) {
            return 0;
        }
        HashMap<Integer, Integer> sumMap = new HashMap<>();
        sumMap.put(0, 0);
        return process(root, 1, sumMap, 0, sum, 0);
    }

    private int process(Node node, int height, HashMap<Integer, Integer> sumMap, int curSum, int sum, int maxLength) {
        if(node == null){
            return maxLength;
        }
        curSum += node.val;
        if (!sumMap.containsKey(curSum)) {
            sumMap.put(curSum, height);
        }
        if (sumMap.containsKey(curSum - sum)) {
            maxLength = Math.max(height - sumMap.get(curSum - sum), maxLength);
        }
        maxLength = process(node.left, height + 1, sumMap, curSum, sum, maxLength);
        maxLength = process(node.right, height + 1, sumMap, curSum, sum, maxLength);
        if (sumMap.get(curSum).equals(height)) {
            sumMap.remove(curSum);
        }
        return maxLength;
    }
}
